This invention relates to a packet transmitting apparatus for transmitting, in order, packets belonging to a plurality of groups having priorities that differ from one another. More particularly, the invention relates to a packet transmitting apparatus such as an IP router or Ethernet switch for switching variable-length packets.
When IP networks (the Internet) first appeared, there was no differentiated processing within the network and there was no processing for giving priority to a certain specific flow when allocating bandwidth. In the initial form of the Internet, bandwidth allocation was on the basis of “first come, first served”, and the more data there was to be sent, the larger the network bandwidth that was occupied. Scheduling logic, therefore, also was simple FIFO (first in, first out).
However, the era has gradually come to expect that IP networks send multimedia information, namely moving images and voice, and not just electronic files, e-mail and still images. Multimedia information such as moving images and voice is traffic in which it is anticipated that the information will be transmitted from the transmission source to the transmission destination “at a certain, fixed bandwidth and fixed period and without loss of data” as the term “real-time traffic” attests. Real-time traffic until now has been traffic in which information is exchanged by so-called telephone networks, wherein communication is carried out after reserving a fixed bandwidth from the transmission source to the transmission destination.
The enormous amount of packet data from an ever increasing number of Internet users has led to packet congestion within the network and many packets are now starting to be discarded because they cannot be processed in the network. Many users are now experiencing a decline in throughput to an extent visible to the eye. This has led to requests that throughput be raised in exchange for the payment of fees higher than those paid by other users. This is often compared to the difference between a common road and a highway. Having a fixed bandwidth assured is equivalent to travel on a highway, while having various traffic scramble for bandwidth is likened to travel on a common road. However, it should be noted that in the case of an IP network, merely assuring traffic on the highway means taking network resources (bandwidth) away from the common road, as a result of which the common road becomes even more congested.
The above-mentioned circumstances have resulted in the need for bandwidth control and priority control in IP networks that aim at effective exploitation of bandwidth by statistical multiplexing. Differentiation on the Internet is now in the process of being defined and established as service policy by QoS (Quality of Service), Diffserve and Intserve, etc. With service policy based upon the idea of differentiation, services for various packet flows are managed by packet-flow classification, stipulation of input-traffic characteristics, stipulation of packet-discard priority and stipulation of bandwidth assurance, etc.
Strict queuing and weighted fair queuing (WFQ) are typical examples of bandwidth control schemes.
Strict queuing is a simple priority scheme in which if a packet is one that has been set to a high priority, the packet is always given precedence and sent first. FIG. 8 is a diagram useful in describing the simple priority scheme, in which numerals 11 to 14 denote clients, 2 a router and 3 an application server. This is for a case where each of the clients 11 to 14 transmits packets to the server 3 via the router 2, where P represents the priority; the larger the value of P, the higher the priority. If packets (1) to (4) enter respective ports from the clients 11 to 14 simultaneously, the router 2 sends the packets to the server 3 in order of decreasing priority which, in FIG. 8, is the order (3)→(2)→(4)→(1).
FIG. 8 is for the simple case, in which packets are no longer transmitted in simple FIFO (first in, first out) order when priority control is carried out. In FIG. 9, it will be understood that packet (5) is transmitted before packet (1) despite the fact that packet (1) arrived before packet (5). Thus, with strict queuing, if packets having a high priority arrive successively, packets of low priority are not sent until the transmission of packets having a higher priority is completed. Consequently, the possibility that a packet of low priority will remain in a queuing memory is high. If there is input beyond a certain threshold, low-priority packets are discarded.
A characterizing feature of strict queuing is that very strict priority control is carried out and scheduling processing also is very easy and simple. However, the setting of bandwidth and the setting of priority cannot be performed with a high degree of freedom between flows.
Weighted fair queuing is a scheme in which priority ratio (weight) is decided using order of priority as an analog parameter, and packets are transmitted in accordance with the ratio decided. FIGS. 10 and 11 are diagrams useful in describing weighted fair queuing. Here clients 11, 12, 13 and 14 are assigned priority ratios of 12.5%, 12.5%, 25% and 50%, respectively, with respect to a single port on the server 3. With weighted fair queuing, bandwidth allocation processing in accordance with the ratios is executed without a strict inclination toward a specific priority as in the case of strict queuing (see FIG. 11).
With weighted fair queuing, however, priority-ratio control is applied to variable-length packets. When weighted control is carried out based upon the number of packets forwarded, the difference between packets of minimum size and maximum size is not recognized. If an Ethernet frame is taken as an example, minimum size is 64 bytes and maximum size is 1522 bytes. If router 2 is to send packets from clients 11 and 12 alternately to server 3, therefore, as shown in FIG. 12, a large difference in which priority-ratio error increases almost 24-fold occurs. A method of solving this problem is to segment variable-length packets into a fixed-length size and perform control based upon the number of transfers of fixed-length data, as shown in FIG. 13.
With this method, however, a problem which arises is that a segmenting processor and a reassembly processor are required respectively in front of and in back of a routing or switching unit (not shown) in the router 2. In particular, it must be assumed that a plurality of packets will undergo reassembly simultaneously in the reassembly processor, logically or physically separate reassembly buffers must be provided for each of these packets and the buffers must be controlled. FIG. 14 is a diagram useful in describing packet transmission control in the router. Shown in FIG. 14 are a packet switch 2a, a scheduler 2b, reassembly buffers 2c1, to 2c4 for reassembling packets from each of the clients, and a packet read-out unit 2d for reading packets out of the buffers.
(1) First Problem
The weighted fair queuing scheme introduces the concept of a virtual clock on a per-packet basis. A virtual clock is the time needed for a packet to be output from a device, i.e., the time during which the packet exists in the device. Virtual clock information must be managed individually packet by packet inside the device, and the generation and management of this information entails a great amount of processing. In other words, the scheduler in weighted fair queuing must generate and manage a great deal of complex control information for all packets that exist inside the device, scheduling processing is complicated and processing time is prolonged.
(2) Second Problem
When a variable-length packet is segmented into fixed-length data such as ATM cells and the scheduler also performs schedule management in units of the fixed-length data, scheduler control is comparatively easy. In order to accomplish this, however, processing for segmenting variable-length packets is required in front of the routing unit and switch unit, and reassembly processing is required in back of the switch unit. Accordingly, it must be kept in mind that a plurality of packets will undergo processing simultaneously in buffers for reassembling a variable-length packet in back of the switch unit, and it is necessary that a logically or physically separate reassembly buffer be provided for each of these packets. A problem which arises is an increase in the scale of the apparatus.
(3) Third Problem
It is desired that physical bandwidth be usable with 100% effectiveness. To achieve this, it is required that a variable-length packet be output to its destination by stuffing in the packet data without leaving needlessly unallocated bandwidth and without any gaps in terms of time. However, with a complicated scheduler arrangement, as in the prior art, the time for a single scheduling processing cycle is prolonged and packet data cannot be output to the output destination without gaps.
(4) Fourth Problem
The conventional scheduler processes queues, which are to undergo scheduling, in a single stage, and the setting of priorities also is performed by setting all queue elements (e.g., packets) as objects to be scheduled. In the conventional schemes, the round-robin method is adopted so that a grant is made to rotate from one queue element to another. The round-robin method is such that if a certain queue element acquires a grant, the priority of this queue element is reduced to the lowest level in the next cycle of scheduling processing. Though the round-robin method is suited to fair scheduling, it cannot be employed as is in non-linear bandwidth allocation control (i.e., in differentiated service). For example, with regard to queue elements the bandwidth of which has been set high, it is necessary to raise the frequency with which transmission grants are given. The conventional round-robin scheduler, however, cannot perform such scheduling control.
(5) Fifth Problem
Physical bandwidth assurance schedulers that handle variable-length packets are classified broadly into two types. One uses a method of performing scheduling by segmenting variable-length packet data into fixed-length data, and other uses a method of performing scheduling using the variable-length packet data as is. The present invention adopts the method of performing scheduling using the variable-length packet data as is. In this method, a transmission grant from a scheduler generally is output in packet units. In this case, the length of packet data transferred by a single transmission grant is not fixed. In other words, even though a single transmission grant is rotated equally among the queue elements, the same physical bandwidth is not occupied. If this takes place several dozen or several hundred times, in the worst case bandwidth allocation to the queue elements becomes unfair regardless of the fact that the transmission grant is caused to rotate among elements the same number of times. This is the reason why bandwidth assurance control is difficult in a scheduler that handles variable-length packets.
(6) Sixth Problem
The fifth problem, namely unfairness in the transmission of variable-length packets, is eliminated by stipulating the transmission assurance bandwidth in a single transmission grant. In this case, it is necessary to stipulate processing in an instance where a packet to be transmitted ceases existing before the assured bandwidth is attained. A method of waiting for arrival of the packet is available as a method of such processing. This is a method of issuing transmission grants continuously to queue elements of interest until the assured bandwidth is attained. However, 100% utilization of physical bandwidth is impossible and the problem of needlessly unallocated bandwidth arises.
(7) Seventh Problem
As mentioned above, a variable-length scheduler cannot use information indicative of packet transfer count in order to implement fair bandwidth allocation. The reason for this is as follows: Even if there are the same ten packets of data, unfairness occurs, despite an identical bandwidth setting, in a case where there are a large number of minimum-size packets from one queue element and a large number of maximum-size packets from another queue element. Accordingly, it is necessary to arrange it so that exact bandwidth control can be carried out even in the case of variable-length packets.